package com.ai.zuochengyun.phase01.class01;

/**
 * 小和问题，右侧比左侧的数的个数*arr[i]之和，可以转换成归并思想求解
 */
public class Code06_SmallSum {

    public static void main(String[] args) {
        int[] arr = new int[]{6, 3, 2, 1, 6, 7};
        int ret = mergeSort(arr);
        System.out.println(ret);
    }

    /**
     * 在0到n-1范围有序
     *
     * @param arr
     */
    private static int mergeSort(int[] arr) {
        if (arr == null || arr.length == 1) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        // 让左侧有序
        int leftPart = process(arr, left, mid);
        // 让右侧有序
        int rightPart = process(arr, mid + 1, right);
        // 让整体有序
        return leftPart + rightPart + merge(arr, left, mid, right);
    }

    private static int merge(int[] arr, int left, int mid, int right) {
        int ans = 0;
        int size = right - left + 1;
        // 创建一个辅助数组
        int[] help = new int[size];
        int index = 0;
        int p1 = left, p2 = mid + 1;

        // 左右都没有越界
        while (p1 <= mid && p2 <= right) {
            // 左侧比右侧小的时候，产生小和
            // 左侧大于等于右侧的时候，不产生小和，先拷贝右侧的值
            if (arr[p1] < arr[p2]) {
                ans += arr[p1] * (right - p2 + 1);
                help[index++] = arr[p1++];
            } else {
                help[index++] = arr[p2++];
            }
        }
        // 左侧还有值
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        // 右侧还有值
        while (p2 <= right) {
            help[index++] = arr[p2++];
        }

        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return ans;
    }
}
